package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 力扣困难987：二叉树的垂序遍历
 */
public class VerticalTraversal {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<>();
        dfs(root,0,0,nodes);
        Collections.sort(nodes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]!=o2[0]){
                    return o1[0] -o2[0];
                }else if(o1[1]!=o2[1]){
                    return o1[1]-o2[1];
                }else{
                    return o1[2]-o2[2];
                }
            }
        });
        List<List<Integer>> ans = new ArrayList<>();
        int size = 0;
        int lastcol = Integer.MIN_VALUE;
        for(int[] tuple:nodes){
            int col = tuple[0],row = tuple[1],value = tuple[2];
            if(col!=lastcol){
                lastcol = col;
                ans.add(new ArrayList<>());
                size++;
            }
            ans.get(size-1).add(value);
        }
        return ans;

    }
    public void dfs(TreeNode node,int row,int col,List<int[]> nodes){
        if(node==null){
            return;
        }
        nodes.add(new int[]{col,row,node.data});
        dfs(node.left,row+1,col-1,nodes);
        dfs(node.right,row+1,col+1,nodes);
    }
}
